/*
 * optibiparti.cpp
 *
 *  Created on: 8 déc. 2011
 *      Author: pmilian
 */
#include "FluxGraph.h"
#include  <queue>
#include <algorithm>

using namespace std;

typedef struct vPair {
	struct vPair *father;
	int current;
} vPair;

int
isInVector(vector<vPair> v, int val) {
	unsigned i;
	for (i= 0; i < v.size(); ++i) {
		if (v[i].current == val) {
			return 1;
		}
	}
	return 0;
}

vector<int> optibiparti(FluxGraph *graph) {
	vector<int> xVertices = graph->getNeighbours(0);
	vector<int> covers;
	vector<vPair> FQueue;
	vector<vPair> NQueue;
	vPair currentVertex;


	unsigned i,j;
	while (true) {
		NQueue.clear();
		FQueue.clear();
		currentVertex.father = NULL;
		currentVertex.current = graph->S;
		FQueue.push_back(currentVertex);
		while (!FQueue.empty()) {
			currentVertex = FQueue.front();
			FQueue.erase(FQueue.begin());
			NQueue.push_back(currentVertex);
			vector<int> neighbours = graph->getNeighbours(currentVertex.current);
			for (i = 0; i < neighbours.size(); ++i) {
				if (neighbours[i] == graph->T) {
					break;
				}
				if (!graph->isTagged(currentVertex.current, neighbours[i]) && !isInVector(FQueue, neighbours[i])) {

					vPair neighbourPair;
					vPair *fatherPair = (vPair*)malloc(sizeof(vPair));
					fatherPair->father = currentVertex.father;
					fatherPair->current = currentVertex.current;

					neighbourPair.father = fatherPair;
					neighbourPair.current = neighbours[i];
					FQueue.push_back(neighbourPair);
				}
			}
			if (i < neighbours.size() && neighbours[i] == graph->T) {
				vPair neighbourPair;
				vPair *fatherPair = (vPair*)malloc(sizeof(vPair));
				fatherPair->father = currentVertex.father;
				fatherPair->current = currentVertex.current;

				currentVertex.father = fatherPair;
				currentVertex.current = neighbours[i];
				break;
			}
		}


		if (FQueue.empty()) {

			for (i = 0; i < NQueue.size(); ++i) {
				vector<int> neighbours = graph->getNeighbours(NQueue[i].current);
				for (j = 0; j < neighbours.size(); ++j) {
					if (neighbours[j] == graph->T) {
						covers.push_back(NQueue[i].current - 2);
					}
				}
			}
			vector<int> Sneighbours = graph->getNeighbours(graph->S);
			for (i = 0; i < Sneighbours.size(); ++i) {
				if (!isInVector(NQueue, Sneighbours[i])) {
					covers.push_back(Sneighbours[i] - 2);
				}
			}
			break;
		} else if (currentVertex.current == graph->T) {
			while (currentVertex.father != NULL) {
				if (currentVertex.current == graph->T || currentVertex.father->current == graph->S) {
					graph->tag(currentVertex.current, currentVertex.father->current);
				} else {
					graph->invertEdge(currentVertex.father->current,currentVertex.current);
				}
				currentVertex = *currentVertex.father;
			}
		}
	}
	return covers;
}

